/**
 * 项目名称: 链式存储.cpp
 * 项目路径: study/DataStructure/数据结构/树/二叉树
 * 编辑时间: 2024年07月30日20时56分38秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;

typedef struct BiTNode {
    int data;
    struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree;

/**
 * 先序遍历
 * @param T
 */
void PreOrder(BiTree T) {
    if (T != nullptr) {
        visit(T);// 访问根结点
        PreOrder(T->lChild);//递归遍历左子树
        PreOrder(T->rChild);//递归遍历右子树
    }
}

/**
 * 中序遍历
 * @param T
 */
void InOrder(BiTree T){
    if(T!= nullptr){
        InOrder(T->lChild);//递归遍历左子树
        visit(T);//访问根节点
        InOrder(T->rChild);//递归遍历右子树
    }
}

/**
 * 后序遍历
 * @param T
 */
void PostOrder(BiTree T){
    if(T!= nullptr){
        PostOrder(T->lChild);//递归遍历左子树
        PostOrder(T->rChild);//递归遍历右子树
        visit(T);//访问根节点
    }
}

/**
 * 非递归中序遍历
 * @param T
 */
void InOrderFF(BiTree T){
    InitStack(S);//初始化栈
    BiTree p = T;//p是遍历指针
    while (p || IsEmpty(S)){
        if(p){
            Push(S,p);//当前结点入栈
            p=p->lChild;//左孩子不空,一直向左走
        }else{
            Pop(S,p);//出栈
            visit(p);
            p=p->rChild;//向右子树走
        }
    }
}

/**
 * 非递归先序遍历
 * @param T
 */
void PreOrderFF(BiTree T){
    InitStack(S);//初始化栈
    BiTree p = T;//p是遍历指针
    while (p || IsEmpty(S)){
        if(p){
            visit(p);
            Push(S,p);//当前结点入栈
            p=p->lChild;//左孩子不空,一直向左走
        }else{
            Pop(S,p);//出栈
            p=p->rChild;//向右子树走
        }
    }
}

/**
 * 层次遍历
 * @param T
 */
void LevelOrder(BiTree T){
    InitQueue(Q);//初始化辅助队列
    BiTree p;
    EnQueue(Q,T);//将根节点入队
    while (!IsEmpty(Q)){
        DeQueue(Q,p);//队头结点出队
        visit(p);
        if(p->lChild!= nullptr)EnQueue(Q,p->lChild);//左孩子不空,则左孩子入队
        if(p->rChild!= nullptr)EnQueue(Q,p->rChild);//右孩子不空,则右孩子入队
    }
}
int main() {
//    add(11,tree, false);
    return 0;
}
